博弈论3 [推理与动态规划]

主题是推理与动态规划
由于是动态更新的,所以标号可能是乱的,不用在意标号问题,标号只是确定说之前更新到哪了
如果超过$15$个题,就会专门再有一个传送门指向其他的文章.

①[POJ 1082] Calendar Game
原题链接：http://poj.org/problem?id=1082
题面就不放了，这题没啥意思，结论是月和天之和为偶数时先手必胜。但是很弱智的是有特例：$9.30$和$11.30$也是先手必胜。

②[POJ 2068] Nim
原题链接：http://poj.org/problem?id=2068
题目大意：有两个队伍，每个队伍有$n$个人，你的队伍先手，即第一个人是你的队伍的人，且标号为$1$，并且两个队伍的人是交替坐成一个圈的。场上一共有$S$个石头，每个人每次取的石头的数量最大值是$M_i$，且不能不取。问你的队伍是否必胜。
数据范围：
多组测试数据
$1 \leq n \leq 10$
$1 \leq M_i \leq 16$
$1 \leq S_i \leq 2^{13}$
样例输入：

1 101 4 4
1 100 4 4
3 97 8 7 6 5 4 3
0

0
1
1

这题看起来没什么性质可推，但是数据量由于人数非常小，可以考虑从原始定义出发：即从一个状态如果走到了一个必败态，则前者是必胜态；若走不到任何一个必败态则必败。用$DP$求解状态即可，整个局面是一个环，定义状态$f[i][j]$为当前是第$i$个人，面对的局面是$j$个石子在场上，若必胜为$1$，否则为$0$。状态的转移也比较好想，但是由于说涉及到环和取模，所以这里就使用记忆化以及求出去的状态的方式来做比较简单。具体来说当前的状态$f[i][j]$取决于当前取了$x$个石块对应的后面一个状态$f[(i + 1) \% (2 * n)][j - x]$里有没有一个必败态，如果有的话就为$1$，如果遍历了所有的都没有，就是$0$。同时因为是一个环，所以为了方便代码的实现就把位置换成了从$0$开始而非从$1$开始、
代码：

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 22,M = 1 << 14;
int f[N][M];
int a[N],n,S;
bool dp(int i,int j)
{
	if(!j)	return 1;
	if(f[i][j] != -1)	return f[i][j];
	
	for(int k = 1;k <= a[i];++k)
	{
		if(j - k < 0)	break;
		if(dp((i + 1) % (2 * n),j - k) == 0)	return f[i][j] = 1;
	}	
	return f[i][j] = 0;
}
int main()
{
	while(scanf("%d",&n),n)
	{
		memset(f,-1,sizeof f);
		scanf("%d",&S);
		for(int i = 0;i < 2 * n;++i)	scanf("%d",&a[i]);
		if(dp(0,S))	puts("1");
		else puts("0");
	}
    return 0;
}

③[POJ 3668] Cheat in the game
原题链接：http://poj.org/problem?id=3688
题目大意：Alice和Bob在玩一个取石子游戏，一共有$n$个卡片和最多$m$个石头，每次两个人都会在$n$张卡片中随机的选出一个，卡片上标记的数字就是本回合要取的石子数量，如果不够取就再抽一张，如果卡片抽完了胜者还没判别出来，则游戏重置再来，直到决出胜者为止。问在最多$m$个石头的前提下，有多少种情况可以先手必胜。输出方案数即可。
数据范围：
多组测试数据
$1 \leq n \leq 10000$
$1 \leq m \leq 100000$
$1 \leq a_i \leq m$
样例输入：

3 8
1 5 7 
0 0

样例输出：

3

这个题的题意写得不够完整，注意卡片在抽出来了之后是不会反回去的，样例的合法数只有三个：$1,5,7$，并且先手必胜的判据是A的胜率是大于$0$，且B的胜率是$0$。虽然游戏可能进行很多次平局导致游戏重开，但是保证B的胜率是0就行了。
最简单也最直接的想法就是枚举所有石头的可能性，于是顺理成章的就想到了$DP$尝试一下看能不能把复杂度降下来。思考之后会发现$DP$也没法避免枚举，而且方法也不是很明确，说明题目还可能还有什么隐藏的判据没有找出来：
这个题目的选取的个数虽然表面上看是随机的，不过实际上，由于要保证B的胜率一定是$0$，所以说还是得考虑有可能的状态：即保证所有的情况下B都是必输的。因此，可以把“选择”这个条件去掉，变成“组合”，这个题最本质的性质就是：在所有情况中，一个数$m$如果只能被奇数个数表示出来，那么他是必胜的，如果只能被偶数个数表示出来，那么他是必败的。其余的情况结局无法判明，但是至少不是必胜的。
因此$DP$就比较好想了：
第一步先要排序，使状态的更新是正确的。
状态：$f[i][j]$表示$i$这个数，在$j=1$时为能被偶数个数表示出来，$j=0$时表示能被奇数个数表示出来。
入口：对于每个$m_i$来说都有$f[m_i][0] = 1$
出口：先手必胜的状态数就是满足f[i][0] == 1 && f[i][1] == 0的数，其中$1 \leq m$
转移：
若$j > m_i$，则有两种：
当$f[j - m_i][0] == 1$时，$f[j][1] = 1$
当$f[j - m_i][1] == 1$时，$f[j][0] = 1$

最后统计答案就可以了。

代码：

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e4+7,M = 1e5+7;
int a[N],f[M][2];
int n,m;
void dp()
{
	sort(a + 1,a + 1 + n);
	f[a[1]][0] = 1;
	for(int i = 2;i <= n;++i)
	{
		for(int j = m;j > a[i];--j)
		{
			if(f[j - a[i]][0])	f[j][1] = 1;
			if(f[j - a[i]][1])	f[j][0] = 1;
		}
		f[a[i]][0] = 1;
	}
}
int main()
{
	while(scanf("%d%d",&n,&m),n || m)
	{
		for(int i = 1;i <= n;++i)	scanf("%d",&a[i]);
		memset(f,0,sizeof f);
		dp();
		int res = 0;
		for(int i = 1;i <= m;++i)
			if(f[i][0] && !f[i][1])	
				++res;
		printf("%d\n",res);
	}
    return 0;
}

④[POJ 1740]A New Stone Game
原题链接：http://poj.org/problem?id=1740
这题原题面写的很垃圾。
题目大意：Alice和Bob在玩一个新的石子游戏，一共有$n$个石碓，每堆石子里不会超过有$100$个石子。每次操作时，选择一个石碓，丢掉里面的一个石子，下一步可以不操作，也可以选出若干个石子放到另外一个当前非空的任意多个石碓里。最后一个拿走剩下所有石碓的人获胜。A先手，问是否先手必胜。
数据范围：
多组测试数据
$1 \leq n \leq 10$
样例输入：

3
2 1 3
2
1 1
0

样例输出：

1
0

这题是个规律题，$n$一共也才$10$个，可以枚举一下找结论：
当$n == 1$时，先手必胜
当$n == 2$时，如果两堆石子完全相同，则对手可以镜像操作，导致先手必败。除此之外先手必胜。
当$n == 3$时，先手把一堆石子全部拿空，可以变成$n == 2$且相同的两堆的状态（是人为的构造两个不相同），因为可以任意分配到还有石子的堆里，所以是一定可以到达的。这样就构造了一个先手必败局面给对手，因此必胜。
当$n==4$时，同$2$可以拓展出一个结论：当$n$为偶数的时候，如果石子可以两两分成两堆相同的组，就是先手必败的。同样，当$n$是奇数是，可以构造出上一个偶数的状态，因此奇数是必胜的。
最后排个序验证一下结论就可以了。
代码：

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 20;
int n,a[N];
int main()
{
	while(scanf("%d",&n),n)
	{
		for(int i = 1;i <= n;++i)	scanf("%d",&a[i]);
		sort(a + 1,a + 1 + n);
		if(n % 2)	printf("1\n");
		else
		{
			int ok = 1;
			for(int i = 1;i + 1 <= n;i += 2)
			{
				if(a[i] != a[i + 1])	
				{
					ok = 0;
					break;
				}
			}
			if(ok)	puts("0");
			else puts("1");
		}
	}
    return 0;
}